5.1.2 Algoritmo de enrutamiento por vector de distancias (DV)
El algoritmo por vector de distancias (DV) es iterativo, asíncrono y distribuido.
- Es distribuido en el sentido de que cada nodo recibe información de uno o más de sus vecinos directamente conectados, realiza un cálculo y luego distribuye los resultados de su cálculo de vuelta a sus vecinos.
- Es iterativo porque este proceso continúa hasta que no hay disponible más información para ser intercambiada entre los vecinos.
- El algoritmo es asíncrono, en el sentido de que no requiere que todos los nodos operen sincronizados entre sí.
Donde
En el algoritmo, de vez en cuando, cada nodo envía una copia de su vector de distancias a cada uno de sus vecinos. Cuando un nodo x recibe un nuevo vector de distancias procedente de cualquiera de sus vecinos v, guarda dicho vector de v y luego utiliza la ecuación de Bellman-Ford para actualizar su propio vector de distancias.
Si el vector de distancias del nodo x ha cambiado como resultado de este paso de actualización, entonces el nodo x enviará su vector de distancias actualizado a cada uno de sus vecinos, lo que puede a su vez actualizar sus propios vectores distancia.
1 Inicialización:
2 for todos los destinos y vecinos de x:
3 Dx(y) = c(x,y)
4 for cada vecino w de x
5 Dw(y) = ∞ para todos los destinos y vecinos de x
6 for cada vecino w de x
7 enviar vector de distancias Dx = [Dx(y): y vecino de x] a w
8
9 while True:
10 wait (hasta ver una variación en el coste de enlace de un vecino w
11 o hasta recibir un vector de distancias de algún vecino w)
12
13 for cada y conocido de x: // pueden haber tanto conocidos vecinos
14 // como conocidos no vecinos
15 Dx(y) = minv vecino de x{c(x,v) + Dv(y)}
16
17 if Dx(y) se modifica para cualquier y conocido de x
18 enviar vector de distancia Dx = [Dx(y): y conocido de x] a
19 todos los vecinos
El proceso de recibir vectores distancia actualizados de los vecinos, recalcular las entradas de la tabla de enrutamiento e informar a los vecinos de los costes modificados de la ruta de coste mínimo hacia un destino continúa hasta que ya no se envían mensajes de actualización. El algoritmo se encuentra en estado de reposo.
Conteo al infinito
Si bien el algoritmo funciona bien con costos de link fijos, cabe destacar lo que sucede cuando el costo de un link cambia en la red. Para ello, se debe considerar dos casos diferentes: cuando un link disminuye, y cuando uno de ellos aumenta.
Para ejemplificar lo que sucede, se presentan las siguientes redes:
En esta oportunidad, se realiza un cambio de costo disminuyendo el link que conecta x e y.
En el tiempo
Esta vez, se aumenta el link que conecta x e y a 60.
En tiempo
Este ciclo de cómputos incorrectos continuará aumentando el valor en una unidad en cada nodo hasta que
Reversa envenenada
Para solucionar este problema, se utiliza la técnica conocida como reversa envenenada. Supóngase que un nodo x debe enviar su vector de distancia a sus vecinos. Supóngase también que el próximo nodo al que se debe enviar el vector es al nodo y. Antes de realizar el envío, el nodo x modificará las entradas del vector de distancia correspondientes a los nodos que alcanza mediante y por el valor “infinito”.
En otros términos, si
No garantiza una solución al problema para topologías complejas.